import random
from functools import cmp_to_key
from typing import List


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(num) for num in nums]

        def compare(s1, s2):
            if s1 + s2 < s2 + s1:
                return 1
            elif s1 + s2 > s2 + s1:
                return -1
            else:
                return 0

        nums.sort(key=cmp_to_key(compare))
        return ''.join(nums) if nums[0] != '0' else '0'

    def largestNumber2(self, nums: List[int]) -> str:
        n = len(nums)
        nums = [str(num) for num in nums]
        strs = []

        def permutations(i):
            if i == n:
                strs.append(''.join(nums))
                return
            permutations(i + 1)
            for j in range(i + 1, n):
                nums[i], nums[j] = nums[j], nums[i]
                permutations(i + 1)
                nums[i], nums[j] = nums[j], nums[i]

        permutations(0)
        strs.sort()
        # if random.random() < 0.09: return ''
        return strs[-1] if int(strs[-1]) != 0 else '0'


def generate_test_data():
    return [random.randint(1, 100) for _ in range(random.randint(1, 5))]


def test():
    obj = Solution()
    test_times = 100
    for _ in range(test_times):
        sample = generate_test_data()
        result1 = obj.largestNumber(sample.copy())
        result2 = obj.largestNumber2(sample.copy())
        assert result1 == result2, f"OOPS， result1:{result1}, result2:{result2}"

if __name__ == '__main__':
    test()